/*
04-树7 二叉搜索树的操作集
分数 30
作者 陈越
单位 浙江大学

本题要求实现给定二叉搜索树的5种常用操作。
函数接口定义：

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

其中BinTree结构定义如下：
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

    函数Insert将X插入二叉搜索树BST并返回结果树的根结点指针；
    函数Delete将X从二叉搜索树BST中删除，并返回结果树的根结点指针；如果X不在树中，则打印一行Not Found并返回原树的根结点指针；
    函数Find在二叉搜索树BST中找到X，返回该结点的指针；如果找不到则返回空指针；
    函数FindMin返回二叉搜索树BST中最小元结点的指针；
    函数FindMax返回二叉搜索树BST中最大元结点的指针。

*/
BinTree Insert( BinTree BST, ElementType X ) {
    if (BST == NULL) {
        BST = (Position) malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
        return BST;
    }
    if (X < BST->Data) {
        BST->Left = Insert(BST->Left, X);
    } else  {
        BST->Right = Insert(BST->Right, X);
    }
    return BST;
}

BinTree Delete( BinTree BST, ElementType X ) {
    // 如果X不在树中，则打印一行Not Found并返回原树的根结点指针；
    if (BST == NULL) {
        printf("Not Found\n");
        return NULL;
    } 
    if (X < BST->Data) {
        BST->Left = Delete(BST->Left, X);
        return BST;
    } 
    if (X > BST->Data) {
        BST->Right = Delete(BST->Right, X);
        return BST;
    } 
    // 已找到要删除的节点
    // 有左右子节点
    if (BST->Left != NULL && BST->Right != NULL) {
        // 在右子树中找最小
        Position t = FindMin(BST->Right);
        BST->Data = t->Data;
        BST->Right = Delete(BST->Right, BST->Data);
        return BST;
    } 
    Position p = NULL;
    if (BST->Right != NULL) {
        p = BST->Right;
    } else if (BST->Left != NULL) {
        p = BST->Left;
    }
    free(BST);
    return p;
}

Position Find( BinTree BST, ElementType X ) {
    if (BST == NULL) {
        return NULL;
    }
    for (Position p = BST; p!=NULL; ) {
        if (p->Data == X) {
            return p;
        }
        if (X < p->Data) {
            p = p->Left;
        } else {
            p = p->Right;
        }
    }
    return NULL;
}

Position FindMin( BinTree BST ) {
    if (BST == NULL) {
        return NULL;
    }
    Position p = BST;
    while (p->Left != NULL) {
        p = p->Left;
    }
    return p;
}

Position FindMax( BinTree BST ) {
    if (BST == NULL) {
        return NULL;
    }
    Position p = BST;
    while (p->Right != NULL) {
        p = p->Right;
    }
    return p;
}
